//279 分割类型题目
/*
给定一个正整数，求其最少可以由几个完全平方数相加构成

输入输出样例
	输入是给定的正整数，输出也是一个正整数，表示输入的数字最少可以由几个完全平方数相
加构成

Input: n = 13
Output: 2

*/
int numSquares(int n)
{
	vector<int> dp(n + 1, INT_MAX);
	dp[0] = 0;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j * j <= i; ++j)
		{
			dp[i] = min(dp[i], dp[i - j * j] + 1);
		}
	}
	return dp[n];
}